﻿using System.Collections.Generic;

namespace Pagination.Storage
{
    public class AvlTree
    {
        private AvlNode avlTree;
        private readonly Stack<AvlNode> stack = new Stack<AvlNode>();

        public AvlNode GetRoot()
        {
            return avlTree;
        }

        private static int GetHeight(AvlNode position)
        {
            if (position == null)
                return -1;
            return position.Height;
        }

        private static int Max(int lhs, int rhs)
        {
            return lhs > rhs ? lhs : rhs;
        }

        private static AvlNode SingleRotateWithLeft(AvlNode k2)
        {
            AvlNode k1;
            k1 = k2.Left;
            k2.Left = k1.Right;
            k2.Count -= k1.Count + 1;
            k1.Right = k2;
            k2.Height = Max(GetHeight(k2.Left), GetHeight(k2.Right)) + 1;
            k1.Height = Max(GetHeight(k1.Left), k2.Height) + 1;
            return k1;
        }

        private static AvlNode SingleRotateWithRight(AvlNode k1)
        {
            AvlNode k2;
            k2 = k1.Right;
            k1.Right = k2.Left;
            k2.Count += k1.Count + 1;
            k2.Left = k1;
            k1.Height = Max(GetHeight(k1.Left), GetHeight(k1.Right)) + 1;
            k2.Height = Max(GetHeight(k2.Right), k1.Height) + 1;
            return k2;
        }

        public static AvlNode DoubleRotateWithLeft(AvlNode k3)
        {
            k3.Left = SingleRotateWithRight(k3.Left);
            return SingleRotateWithLeft(k3);
        }

        private static AvlNode DoubleRotateWithRight(AvlNode k1)
        {
            k1.Right = SingleRotateWithLeft(k1.Right);
            return SingleRotateWithRight(k1);
        }

        public void Insert(int value)
        {
            avlTree = Insert(value, avlTree);
        }

        private AvlNode Insert(int value, AvlNode t)
        {
            if (t == null)
            {
                t = new AvlNode(value);
                return t;
            }
            stack.Clear();
            while (true)
            {
                if (value <= t.Value)
                {
                    t.Count++;
                    if (t.Left != null)
                    {
                        stack.Push(t);
                        t = t.Left;
                    }
                    else
                    {
                        t.Left = new AvlNode(value);
                        break;
                    }
                }
                else
                {
                    if (t.Right != null)
                    {
                        stack.Push(t);
                        t = t.Right;
                    }
                    else
                    {
                        t.Right = new AvlNode(value);
                        break;
                    }
                }
            }

            while (stack.Count != 0)
            {
                t = stack.Pop();

                if (value <= t.Value)
                {
                    if (GetHeight(t.Left) - GetHeight(t.Right) == 2)
                        t = value <= t.Left.Value ? SingleRotateWithLeft(t) : DoubleRotateWithLeft(t);
                }
                else if (value > t.Value)
                {
                    if (GetHeight(t.Right) - GetHeight(t.Left) == 2)
                        t = value >= t.Right.Value ? SingleRotateWithRight(t) : DoubleRotateWithRight(t);
                }
                BindToParent(t, value, stack);
                t.Height = Max(GetHeight(t.Left), GetHeight(t.Right)) + 1;
            }
            return t;
        }

        private static void BindToParent(AvlNode t, int value, Stack<AvlNode> stack)
        {
            if (stack.Count != 0)
                if (value <= stack.Peek().Value)
                    stack.Peek().Left = t;
                else
                    stack.Peek().Right = t;
        }
    }
}